package LeetCode.LeetCode2;

/**
 * @author lumin
 * @date 2022/05/19 16:41
 **/
public class Num240 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        if(matrix.length == 1){
            return BinarySearch(matrix[0],target);
        }
        if(matrix[0].length == 1){
            return BinarySearch(matrix[0],target);
        }
        int i = 0;
        while(i < matrix.length){
            int j = i;
            if(matrix[i][i] < target){
                i++;
            }else if(matrix[i][i] == target){
                return true;
            }else{
                return BinarySearch(matrix[i],target) || BinarySearch(matrix[j],target);
            }
        }
        return false;
    }

    private boolean BinarySearch(int[] matrix, int target) {
        int i = 0;
        int j = matrix.length;
        while(i <= j){
            int mid = (i + j) >> 1;
            if(matrix[mid] < target){
                i = mid + 1;
            }else if(matrix[mid] == target){
                return true;
            }else{
                j = mid - 1;
            }
        }
        return false;
    }
}